﻿// 4221. 洗牌.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <string>
#include <map>
#include <queue>



using namespace std;
/*
https://www.acwing.com/problem/content/4224/


给定两叠纸牌 S1 和 S2，每叠恰好有 C张牌。

每张牌的尺寸大小都完全相同，但是颜色可能不同。

下面介绍洗牌规则。

不妨设 S1中纸牌从上到下编号依次为 a1,a2,…,aC
，S2 中纸牌从上到下编号依次为 b1,b2,…,bC。

洗牌就是将这两叠牌交错堆叠在一起，形成一个拥有 2C张牌的新牌堆 S12。

新牌堆中的牌由上至下依次为 a1,b1,a2,b2,…,aC,bC。

可参考下图：

3087_1.png

然后，将牌堆从中间一分为二，下半部分是新的 S1，上半部分是新的 S2。

这样就可以继续进行洗牌操作获得新的 S12了。

给定 S1和 S2，请问至少需要进行多少轮洗牌操作方可获得指定牌堆 S12。

输入格式
第一行包含一个整数 T，表示共有 T 组测试数据。

每组数据第一行包含一个整数 C。

第二行包含一个长度为 C的由大写字母构成的字符串，其中第 i个字母表示初始 S1
 中由底向上第 i张牌的颜色。

第三行包含一个长度为 C的由大写字母构成的字符串，其中第 i
 个字母表示初始 S2中由底向上第 i张牌的颜色。

第四行包含一个长度为 2C 的由大写字母构成的字符串，其中第 i
 个字母表示目标 S12中由底向上第 i张牌的颜色。

输出格式
共 T行，每行输出一组数据的结果，首先输出组别编号 i
（从 1开始），然后输出所需要的最少洗牌次数。如果无法通过洗牌获得目标牌堆，则输出 −1。

数据范围
1≤T≤1000,
1≤C≤100。

卡牌最多有 8 种颜色，用大写字母 A∼H表示，所以输入字符串中不会出现其他大写字母。

输入样例：
2
4
AHAH
HAHA
HHAAAAHH
3
CDE
CDE
EEDDCC
输出样例：
1 2
2 -1
*/


int t, n, group;
string A, B, target;
map<string, int> vis;

string doCard(string a, string b) {
	string ret;
	for (int i = 0; i < a.size(); i++) {
		ret.push_back(b[i]);
		ret.push_back(a[i]);
	}

	return ret;
}

void solve() {
	//第一次洗牌
	vis.clear();
	string curr = doCard(A, B);
	queue<string> q; q.push(curr); vis[curr] = 1;

	while (!q.empty()) {
		curr = q.front(); q.pop();
		int step = vis[curr];

		if (curr == target) {
			cout << group << " " << step << endl; return;
		}

		int n = A.size();
		A = curr.substr(0, n);
		B = curr.substr(n);
		curr = doCard(A, B);
		if (vis.count(curr) == 0) {
			vis[curr] = step + 1;
			q.push(curr);
		}
	}

	cout << group << " -1" << endl;
}

int main()
{
	cin >> t;
	for (group = 1; group <= t; group++) {
		cin >> n >> A >> B >> target;
		solve();
	}


	return 0;
}

